package com.cdcas.tree;

public class BinaryTreeImpl<E> implements IBinaryTree<E> {
    private class Node{
        private Comparable<E> data;
        private Node left;
        private Node right;
        private Node parent;
        public Node(Comparable<E> data) {
            this.data = data;
        }
        public void toArrayNode() {
            if (this.left !=null) {
                this.left.toArrayNode();
            }
            BinaryTreeImpl.this.data[BinaryTreeImpl.this.foot++] = (E)this.data;
            if (this.right!= null) {
                this.right.toArrayNode();
            }
        }
    }
    private Node root;

    //添加属性
    private int count;
    private int foot;
    private Object[] data;


    @Override
    public void add(E data) {
        if (data ==null) {
            throw new NullPointerException("存储在二叉树结构中的数据不允许为null");
        }
        if (!(data instanceof Comparable)){
            throw new ClassCastException("数据对象所在类没有实现Comparable接口");
        }
        Node newNode = new Node((Comparable) data);
        if (this.root == null) {
            this.root = newNode;
        } else {
            Node currentNode = this.root;
            while (currentNode != newNode) {
                if (currentNode.data.compareTo(data) <=0) {
                    if (currentNode.right != null) {
                        currentNode = currentNode.right;
                    } else {
                        currentNode.right = newNode;
                        newNode.parent = currentNode;
                        currentNode = newNode;
                    }
                } else {
                    if (currentNode.left != null) {
                        currentNode = currentNode.left;

                    }else {
                        currentNode.left = newNode;
                        newNode.parent = currentNode;
                        currentNode = newNode;
                    }
                }
            }
        }
        this.count ++;
    }

    @Override
    public int size() {
        return this.count;
    }

    @Override
    public Object[] toArray() {
        if (this.size() == 0) {
            return null;
        }
        this.data = new Object[size()];
        this.foot = 0;
        this.root.toArrayNode();
        return this.data;
    }
}
